package cn.zifangsky.array.questions;

import cn.zifangsky.linkedlist.LinkedList;
import org.junit.Assert;
import org.junit.Test;

/**
 * <p>求最大值减去最小值小于或等于num的子数组数量</p><br/>
 *
 * <p>【题目】给定数组arr和整数num，共返回有多少个子数组满足如下情况：</p>
 * <p>max(arr[i..j]) - min(arr[i..j]) <= num</p>
 * <p>max(arr[i..j])表示子数组arr[i..j]中的最大值，min(arr[i..j])表示子数组arr[i..j]中的最小值。</p><br/>
 *
 * <p>【要求】如果数组长度为N ，请实现时间复杂度为O (N )的解法。</p>
 *
 * @author zifangsky
 * @date 2019/12/31
 * @since 1.0.0
 */
public class Problem_004_AllSubarraysLessThanNum {

    @Test
    public void testMethods(){
        //定义阈值num
        int num = 2;
        //定义三个测试数组
        int[] arr1 = {4, 3, 6, 7};
        int[] arr2 = {4, 3, 6, 7, 9};
        int[] arr3 = {6, 5, 2, 3, 4, 4, 8, 7, 5, 3, 7, 7, 4, 2, 5, 7, 9, 2, 4, 4};

        //断言测试结果是否准确
        Assert.assertEquals(6, this.getNum(arr1, num));
        Assert.assertEquals(8, this.getNum(arr2, num));
        Assert.assertEquals(37, this.getNum(arr3, num));
    }

    /**
     * <p>获取满足条件的子数组数量</p>
     *
     * <p>求解原理：<b>如果子数组arr[i..j]满足条件，即max(arr[i..j])-min(arr[i..j])<=num，那么arr[i..j]中的每一个子数组，即arr[k..l](i<=k<=l<=j)都满足条件。</b>
     * 我们以子数组arr[i..j-1]为例说明，arr[i..j-1]最大值只可能小于或等于arr[i..j]的最大值，arr[i..j-1]最小值只可能大于或等于arr[i..j]的最小值，
     * 所以arr[i..j-1]必然满足条件。同理，arr[i..j]中的每一个子数组都满足条件。</p>
     *
     * @author zifangsky
     * @date 2019/12/31 16:48
     * @since 1.0.0
     * @param arr 数组
     * @param threshold 阈值
     * @return int
     */
    private int getNum(int[] arr, int threshold){
        if(arr == null || arr.length == 0){
            return 0;
        }

        //1. 分别定义存储窗口子数组的最大值和最小值的双端队列，定义返回的子数组数量
        LinkedList<Integer> minList = new LinkedList<>();
        LinkedList<Integer> maxList = new LinkedList<>();
        int result = 0;

        //子数组的起始位置
        int i = 0;
        //子数组的结束位置
        int j = 0;
        while (i < arr.length){
            //结束位置不断向右移动
            while (j < arr.length){
                //2. 对于最小值队列，如果队列的对尾元素大于等于arr[i]，则一直做出队操作
                while (!minList.isEmpty() && arr[minList.peekLast()] >= arr[j]){
                    minList.pollLast();
                }

                //3. 新的较小元素的下标从对尾入队
                minList.offerLast(j);

                //4. 对于最大值队列，如果队列的对尾元素小于等于arr[i]，则一直做出队操作
                while (!maxList.isEmpty() && arr[maxList.peekLast()] <= arr[j]){
                    maxList.pollLast();
                }

                //5. 新的较大元素的下标从对尾入队
                maxList.offerLast(j);

                //6.1 如果当前考察的子数组的最大值与最小值之间的差值大于指定阈值，则本次查找的满足条件的子数组为：arr[i] ~ arr[j-1]
                if((arr[maxList.peekFirst()] - arr[minList.peekFirst()]) > threshold){
                    break;
                }

                //6.2 否则当前考察的子数组的结束位置继续向右移动
                j++;
            }

            //7. 计算子数组（arr[i] ~ arr[j-1]）的长度，以及当前子数组的所有两个元素及以上的子数组的数目（理由见方法注释）
            int subArrLength = (j - i);
            int subArrNum = subArrLength * (subArrLength - 1) / 2;
            result += subArrNum;

            //8. 如果本次查找存在子数组（也就是：i < j - 1），将下标 i 和 j 移动到 j - 1 的位置继续查找（因为arr[j-1] ~ arr[j]可能满足条件）
            //否则将下标 i 移动到 j 位置，然后继续查找满足条件的子数组
            if(subArrLength > 1){
                i = j - 1;
                j = i;
            }else{
                i = j;
            }

            minList = new LinkedList<>();
            maxList = new LinkedList<>();
        }

        //9. 由于每个元素构成的子数组同样满足条件，因此最后返回结果时还需要加上初始数组的长度
        return result + arr.length;
    }

}
